#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "linked_list.h"

struct LinkedListIterator {
	void * data;
	LinkedListIterator * prev;
	LinkedListIterator * next;
};

struct LinkedList {
	LinkedListIterator * end;
	FunctionEqualTo equalTo;
	FunctionOnInserted onInserted;
	FunctionOnErased onErased;
};

// LinkedListIterator {

static LinkedListIterator * linkedListIteratorNew(const void * data);

static void linkedListIteratorDelete(LinkedListIterator * iterator);

// }

// LinkedListIterator {

static LinkedListIterator * linkedListIteratorNew(const void * data) {
	LinkedListIterator * tmp;

	tmp = (LinkedListIterator *)malloc(sizeof(LinkedListIterator));
	if (tmp == NULL) {
		return NULL;
	}
	memset(tmp, 0, sizeof(LinkedListIterator));

	tmp->data = (void *)data;
	tmp->prev = NULL;
	tmp->next = NULL;

	return tmp;
}

static void linkedListIteratorDelete(LinkedListIterator * iterator) {
	free(iterator);
}

void * linkedListIteratorData(const LinkedListIterator * iterator) {
	assert(iterator != NULL);

	return iterator->data;
}

LinkedListIterator * linkedListIteratorPrev(const LinkedListIterator * iterator) {
	assert(iterator != NULL);

	return iterator->prev;
}

LinkedListIterator * linkedListIteratorNext(const LinkedListIterator * iterator) {
	assert(iterator != NULL);

	return iterator->next;
}

// }

// LinkedList {

LinkedList * linkedListNew(FunctionEqualTo equalTo, FunctionOnInserted onInserted, FunctionOnErased onErased) {
	LinkedList * tmp;

	tmp = (LinkedList *)malloc(sizeof(LinkedList));
	if (tmp == NULL) {
		return NULL;
	}
	memset(tmp, 0, sizeof(LinkedList));

	tmp->end = linkedListIteratorNew(NULL);
	if (tmp->end == NULL) {
		free(tmp);
		return NULL;
	}
	tmp->end->prev = tmp->end;
	tmp->end->next = tmp->end;
	if (equalTo != NULL) {
		tmp->equalTo = equalTo;
	}
	else {
		tmp->equalTo = functionVoidEqualTo;
	}
	tmp->onInserted = onInserted;
	tmp->onErased = onErased;

	return tmp;
}

void linkedListDelete(LinkedList * list) {
	linkedListClear(list);
	linkedListIteratorDelete(linkedListEnd(list));
	free(list);
}

LinkedListIterator * linkedListBegin(const LinkedList * list) {
	assert(list != NULL);

	return list->end->next;
}

LinkedListIterator * linkedListEnd(const LinkedList * list) {
	assert(list != NULL);

	return list->end;
}

int linkedListIsEmpty(const LinkedList * list) {
	return linkedListBegin(list) == linkedListEnd(list);
}

void linkedListClear(LinkedList * list) {
	while (!linkedListIsEmpty(list)) {
		linkedListErase(list, linkedListBegin(list));
	}
}

LinkedListIterator * linkedListInsert(LinkedList * list, LinkedListIterator * position, const void * data) {
	LinkedListIterator * tmp;

	assert(list != NULL);

	if (position == NULL) {
		return NULL;
	}

	tmp = linkedListIteratorNew(data);
	if (tmp == NULL) {
		return NULL;
	}

	tmp->prev = position->prev;
	tmp->next = position;
	tmp->prev->next = tmp;
	position->prev = tmp;

	if (list->onInserted != NULL) {
		list->onInserted(data);
	}

	return tmp;
}

LinkedListIterator * linkedListErase(LinkedList * list, LinkedListIterator * position) {
	void * data;
	LinkedListIterator * next;

	assert(list != NULL);

	if (position == NULL) {
		return NULL;
	}

	next = position->next;
	if (next == NULL) {
		return NULL;
	}
	data = linkedListIteratorData(position);

	position->prev->next = position->next;
	position->next->prev = position->prev;
	linkedListIteratorDelete(position);

	if (list->onErased != NULL) {
		list->onErased(data);
	}

	return next;
}

LinkedListIterator * linkedListFind(const LinkedList * list, const void * data) {
	return linkedListFindIn(list, linkedListBegin(list), linkedListEnd(list), data);
}

LinkedListIterator * linkedListFindIn(const LinkedList * list, const LinkedListIterator * first, const LinkedListIterator * last, const void * data) {
	assert(list != NULL);

	return linkedListFindInIf(list, first, last, data, list->equalTo);
}

LinkedListIterator * linkedListFindIf(const LinkedList * list, const void * key, FunctionEqualTo equalTo) {
	return linkedListFindInIf(list, linkedListBegin(list), linkedListEnd(list), key, equalTo);
}

LinkedListIterator * linkedListFindInIf(const LinkedList * list, const LinkedListIterator * first, const LinkedListIterator * last, const void * key, FunctionEqualTo equalTo) {
	const LinkedListIterator * current;

	assert(list != NULL && first != NULL && last != NULL && equalTo != NULL);

	for (current = first; current != last; current = linkedListIteratorNext(current)) {
		if (equalTo(linkedListIteratorData(current), key)) {
			return (LinkedListIterator *)current;
		}
	}

	return NULL;
}

void linkedListSplice(const LinkedList * list, LinkedListIterator * position, const LinkedList * another) {
	if (linkedListIsEmpty(another)) {
		return;
	}

	linkedListSpliceIn(list, position, another, linkedListBegin(another), linkedListEnd(another));
}

void linkedListSpliceAt(const LinkedList * list, LinkedListIterator * position, const LinkedList * another, LinkedListIterator * iterator) {
	if (position == iterator || position == linkedListIteratorNext(iterator)) {
		return;
	}

	linkedListSpliceIn(list, position, another, iterator, linkedListIteratorNext(iterator));
}

void linkedListSpliceIn(const LinkedList * list, LinkedListIterator * position, const LinkedList * another, LinkedListIterator * first, LinkedListIterator * last) {
	if (first == last) {
		return;
	}

	linkedListTransfer(list, position, another, first, last);
}

void linkedListTransfer(const LinkedList * list, LinkedListIterator * position, const LinkedList * another, LinkedListIterator * first, LinkedListIterator * last) {
	LinkedListIterator * tmp;

	assert(list != NULL && position != NULL && another != NULL && first != NULL && last != NULL);

	if (position == last) {
		return;
	}

	position->prev->next = (LinkedListIterator *)first;
	last->prev->next = (LinkedListIterator *)position;
	first->prev->next = (LinkedListIterator *)last;

	tmp = position->prev;
	position->prev = last->prev;
	last->prev = first->prev;
	first->prev = tmp;
}

void linkedListMarge(const LinkedList * list, const LinkedList * another) {
	LinkedListIterator * iterator1 = linkedListBegin(list);
	LinkedListIterator * iterator2 = linkedListBegin(another);
	while (iterator1 != linkedListEnd(list)) {
		if (linkedListIteratorData(iterator1) > linkedListIteratorData(iterator2)) {
			do {
				iterator2 = linkedListIteratorNext(iterator2);
			} while (iterator2 != linkedListEnd(another) && linkedListIteratorData(iterator1) < linkedListIteratorData(iterator2));
			if (iterator2 == linkedListEnd(another)) {
				break;
			}
			linkedListSpliceIn(list, iterator1, another, linkedListBegin(another), iterator2);
		}
		iterator1 = linkedListIteratorNext(iterator1);
	}
	linkedListSplice(list, iterator1, another);
}

// }

// LinkedListForInt {

LinkedList * linkedListForIntNew() {
	return linkedListNew(functionIntEqualTo, NULL, functionIntOnErased);
}

LinkedListIterator * linkedListForIntInsert(LinkedList * list, LinkedListIterator * position, int data) {
	int * tmp;

	tmp = (int *)malloc(sizeof(int));
	if (tmp == NULL) {
		return NULL;
	}
	*tmp = data;

	return linkedListInsert(list, position, tmp);
}

LinkedListIterator * linkedListForIntFind(const LinkedList * list, int data) {
	return linkedListFind(list, &data);
}

LinkedListIterator * linkedListForIntFindIn(const LinkedList * list, const LinkedListIterator * first, const LinkedListIterator * last, int data) {
	return linkedListFindIn(list, first, last, &data);
}

// }

// LinkedListForUInt {

LinkedList * linkedListForUIntNew() {
	return linkedListNew(functionUIntEqualTo, NULL, functionUIntOnErased);
}

LinkedListIterator * linkedListForUIntInsert(LinkedList * list, LinkedListIterator * position, unsigned int data) {
	unsigned int * tmp;

	tmp = (unsigned int *)malloc(sizeof(unsigned int));
	if (tmp == NULL) {
		return NULL;
	}
	*tmp = data;

	return linkedListInsert(list, position, tmp);
}

LinkedListIterator * linkedListForUIntFind(const LinkedList * list, unsigned int data) {
	return linkedListFind(list, &data);
}

LinkedListIterator * linkedListForUIntFindIn(const LinkedList * list, const LinkedListIterator * first, const LinkedListIterator * last, unsigned int data) {
	return linkedListFindIn(list, first, last, &data);
}

// }
